package LeetCode;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}15:30
 */
public class E11 {
    public static class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        ListNode result = new E11().getKthFromEnd(head,1);
        while (result!=null){
            System.out.println(result.val);
            result = result.next;
        }
    }

    public ListNode getKthFromEnd(ListNode head, int k) {
        //直接的算出长度的方式
//        if (k < 0){
//            return null;
//        }
//        ListNode temp = head;
//        int length = 0;
//        while (temp!=null){
//            length++;
//            temp = temp.next;
//        }
//        temp = head;
//        for (int i = 0; i < length - k;i++){
//            temp = temp.next;
//        }
//        return temp;


        //双指针的方法
        if (k < 0){
            return null;
        }
        ListNode temp1 = head;
        ListNode temp2 = head;
        for (int i = 0; i < k&&temp1!=null; i++){
            temp1 = temp1.next;
        }
        while (temp1!=null){
            temp1 = temp1.next;
            temp2 = temp2.next;
        }
        return temp2;
    }
}
